// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_OBJECTS_ORDERED_HASH_TABLE_H_
#define V8_OBJECTS_ORDERED_HASH_TABLE_H_

#include "src/base/export-template.h"
#include "src/globals.h"
#include "src/objects/fixed-array.h"
#include "src/objects/js-objects.h"
#include "src/objects/smi.h"
#include "src/roots.h"

// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"

namespace v8 {
namespace internal {

    // OrderedHashTable is a HashTable with Object keys that preserves
    // insertion order. There are Map and Set interfaces (OrderedHashMap
    // and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
    //
    // Only Object keys are supported, with Object::SameValueZero() used as the
    // equality operator and Object::GetHash() for the hash function.
    //
    // Based on the "Deterministic Hash Table" as described by Jason Orendorff at
    // https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
    // Originally attributed to Tyler Close.
    //
    // Memory layout:
    //   [0] : Prefix
    //   [kPrefixSize]: element count
    //   [kPrefixSize + 1]: deleted element count
    //   [kPrefixSize + 2]: bucket count
    //   [kPrefixSize + 3..(3 + NumberOfBuckets() - 1)]: "hash table",
    //                            where each item is an offset into the
    //                            data table (see below) where the first
    //                            item in this bucket is stored.
    //   [kPrefixSize + 3 + NumberOfBuckets()..length]: "data table", an
    //                            array of length Capacity() * kEntrySize,
    //                            where the first entrysize items are
    //                            handled by the derived class and the
    //                            item at kChainOffset is another entry
    //                            into the data table indicating the next
    //                            entry in this hash bucket.
    //
    // When we transition the table to a new version we obsolete it and reuse parts
    // of the memory to store information how to transition an iterator to the new
    // table:
    //
    // Memory layout for obsolete table:
    //   [0] : Prefix
    //   [kPrefixSize + 0]: bucket count
    //   [kPrefixSize + 1]: Next newer table
    //   [kPrefixSize + 2]: Number of removed holes or -1 when the table was
    //                      cleared.
    //   [kPrefixSize + 3..(3 + NumberOfRemovedHoles() - 1)]: The indexes
    //                      of the removed holes.
    //   [kPrefixSize + 3 + NumberOfRemovedHoles()..length]: Not used
    template <class Derived, int entrysize>
    class OrderedHashTable : public FixedArray {
    public:
        // Returns an OrderedHashTable (possibly |table|) with enough space
        // to add at least one new element.
        static Handle<Derived> EnsureGrowable(Isolate* isolate,
            Handle<Derived> table);

        // Returns an OrderedHashTable (possibly |table|) that's shrunken
        // if possible.
        static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);

        // Returns a new empty OrderedHashTable and records the clearing so that
        // existing iterators can be updated.
        static Handle<Derived> Clear(Isolate* isolate, Handle<Derived> table);

        // Returns true if the OrderedHashTable contains the key
        static bool HasKey(Isolate* isolate, Derived table, Object key);

        // Returns a true value if the OrderedHashTable contains the key and
        // the key has been deleted. This does not shrink the table.
        static bool Delete(Isolate* isolate, Derived table, Object key);

        int FindEntry(Isolate* isolate, Object key);

        int NumberOfElements() const
        {
            return Smi::ToInt(get(NumberOfElementsIndex()));
        }

        int NumberOfDeletedElements() const
        {
            return Smi::ToInt(get(NumberOfDeletedElementsIndex()));
        }

        // Returns the number of contiguous entries in the data table, starting at 0,
        // that either are real entries or have been deleted.
        int UsedCapacity() const
        {
            return NumberOfElements() + NumberOfDeletedElements();
        }

        int NumberOfBuckets() const
        {
            return Smi::ToInt(get(NumberOfBucketsIndex()));
        }

        // Returns an index into |this| for the given entry.
        int EntryToIndex(int entry)
        {
            return HashTableStartIndex() + NumberOfBuckets() + (entry * kEntrySize);
        }

        int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }

        int HashToEntry(int hash)
        {
            int bucket = HashToBucket(hash);
            Object entry = this->get(HashTableStartIndex() + bucket);
            return Smi::ToInt(entry);
        }

        int NextChainEntry(int entry)
        {
            Object next_entry = get(EntryToIndex(entry) + kChainOffset);
            return Smi::ToInt(next_entry);
        }

        // use KeyAt(i)->IsTheHole(isolate) to determine if this is a deleted entry.
        Object KeyAt(int entry)
        {
            DCHECK_LT(entry, this->UsedCapacity());
            return get(EntryToIndex(entry));
        }

        bool IsObsolete() { return !get(NextTableIndex())->IsSmi(); }

        // The next newer table. This is only valid if the table is obsolete.
        Derived NextTable() { return Derived::cast(get(NextTableIndex())); }

        // When the table is obsolete we store the indexes of the removed holes.
        int RemovedIndexAt(int index)
        {
            return Smi::ToInt(get(RemovedHolesIndex() + index));
        }

        // The extra +1 is for linking the bucket chains together.
        static const int kEntrySize = entrysize + 1;
        static const int kChainOffset = entrysize;

        static const int kNotFound = -1;
        static const int kMinCapacity = 4;

        static constexpr int PrefixIndex() { return 0; }

        static constexpr int NumberOfElementsIndex() { return Derived::kPrefixSize; }

        // The next table is stored at the same index as the nof elements.
        static constexpr int NextTableIndex() { return NumberOfElementsIndex(); }

        static constexpr int NumberOfDeletedElementsIndex()
        {
            return NumberOfElementsIndex() + 1;
        }

        static constexpr int NumberOfBucketsIndex()
        {
            return NumberOfDeletedElementsIndex() + 1;
        }

        static constexpr int HashTableStartIndex()
        {
            return NumberOfBucketsIndex() + 1;
        }

        static constexpr int RemovedHolesIndex() { return HashTableStartIndex(); }

        static constexpr int NumberOfElementsOffset()
        {
            return FixedArray::OffsetOfElementAt(NumberOfElementsIndex());
        }

        static constexpr int NextTableOffset()
        {
            return FixedArray::OffsetOfElementAt(NextTableIndex());
        }

        static constexpr int NumberOfDeletedElementsOffset()
        {
            return FixedArray::OffsetOfElementAt(NumberOfDeletedElementsIndex());
        }

        static constexpr int NumberOfBucketsOffset()
        {
            return FixedArray::OffsetOfElementAt(NumberOfBucketsIndex());
        }

        static constexpr int HashTableStartOffset()
        {
            return FixedArray::OffsetOfElementAt(HashTableStartIndex());
        }

        static const int kLoadFactor = 2;

        // NumberOfDeletedElements is set to kClearedTableSentinel when
        // the table is cleared, which allows iterator transitions to
        // optimize that case.
        static const int kClearedTableSentinel = -1;
        static constexpr int MaxCapacity()
        {
            return (FixedArray::kMaxLength - HashTableStartIndex()) / (1 + (kEntrySize * kLoadFactor));
        }

    protected:
        // Returns an OrderedHashTable with a capacity of at least |capacity|.
        static Handle<Derived> Allocate(
            Isolate* isolate, int capacity,
            AllocationType allocation = AllocationType::kYoung);
        static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
            int new_capacity);

        void SetNumberOfBuckets(int num)
        {
            set(NumberOfBucketsIndex(), Smi::FromInt(num));
        }

        void SetNumberOfElements(int num)
        {
            set(NumberOfElementsIndex(), Smi::FromInt(num));
        }

        void SetNumberOfDeletedElements(int num)
        {
            set(NumberOfDeletedElementsIndex(), Smi::FromInt(num));
        }

        // Returns the number elements that can fit into the allocated buffer.
        int Capacity() { return NumberOfBuckets() * kLoadFactor; }

        void SetNextTable(Derived next_table) { set(NextTableIndex(), next_table); }

        void SetRemovedIndexAt(int index, int removed_index)
        {
            return set(RemovedHolesIndex() + index, Smi::FromInt(removed_index));
        }

        OBJECT_CONSTRUCTORS(OrderedHashTable, FixedArray);

    private:
        friend class OrderedNameDictionaryHandler;
    };

    class V8_EXPORT_PRIVATE OrderedHashSet
        : public OrderedHashTable<OrderedHashSet, 1> {
    public:
        DECL_CAST(OrderedHashSet)

        static Handle<OrderedHashSet> Add(Isolate* isolate,
            Handle<OrderedHashSet> table,
            Handle<Object> value);
        static Handle<FixedArray> ConvertToKeysArray(Isolate* isolate,
            Handle<OrderedHashSet> table,
            GetKeysConversion convert);
        static Handle<OrderedHashSet> Rehash(Isolate* isolate,
            Handle<OrderedHashSet> table,
            int new_capacity);
        static Handle<OrderedHashSet> Allocate(
            Isolate* isolate, int capacity,
            AllocationType allocation = AllocationType::kYoung);
        static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
        static inline RootIndex GetMapRootIndex();
        static inline bool Is(Handle<HeapObject> table);
        static const int kPrefixSize = 0;

        OBJECT_CONSTRUCTORS(OrderedHashSet, OrderedHashTable<OrderedHashSet, 1>);
    };

    class V8_EXPORT_PRIVATE OrderedHashMap
        : public OrderedHashTable<OrderedHashMap, 2> {
    public:
        DECL_CAST(OrderedHashMap)

        // Returns a value if the OrderedHashMap contains the key, otherwise
        // returns undefined.
        static Handle<OrderedHashMap> Add(Isolate* isolate,
            Handle<OrderedHashMap> table,
            Handle<Object> key, Handle<Object> value);

        static Handle<OrderedHashMap> Allocate(
            Isolate* isolate, int capacity,
            AllocationType allocation = AllocationType::kYoung);
        static Handle<OrderedHashMap> Rehash(Isolate* isolate,
            Handle<OrderedHashMap> table,
            int new_capacity);
        Object ValueAt(int entry);

        // This takes and returns raw Address values containing tagged Object
        // pointers because it is called via ExternalReference.
        static Address GetHash(Isolate* isolate, Address raw_key);

        static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
        static inline RootIndex GetMapRootIndex();
        static inline bool Is(Handle<HeapObject> table);

        static const int kValueOffset = 1;
        static const int kPrefixSize = 0;

        OBJECT_CONSTRUCTORS(OrderedHashMap, OrderedHashTable<OrderedHashMap, 2>);
    };

    // This is similar to the OrderedHashTable, except for the memory
    // layout where we use byte instead of Smi. The max capacity of this
    // is only 254, we transition to an OrderedHashTable beyond that
    // limit.
    //
    // Each bucket and chain value is a byte long. The padding exists so
    // that the DataTable entries start aligned. A bucket or chain value
    // of 255 is used to denote an unknown entry.
    //
    // The prefix size is calculated as the kPrefixSize * kTaggedSize.
    //
    // Memory layout: [ Prefix ] [ Header ]  [ Padding ] [ DataTable ] [ HashTable ]
    // [ Chains ]
    //
    // The index are represented as bytes, on a 64 bit machine with
    // kEntrySize = 1, capacity = 4 and entries = 2:
    //
    // [ 0 ] : Prefix
    //
    // Note: For the sake of brevity, the following start with index 0
    // but, they actually start from kPrefixSize * kTaggedSize to
    // account for the the prefix.
    //
    // [ Header ]  :
    //    [0] : Number of elements
    //    [1] : Number of deleted elements
    //    [2] : Number of buckets
    //
    // [ Padding ] :
    //    [3 .. 7] : Padding
    //
    // [ DataTable ] :
    //    [8  .. 15] : Entry 1
    //    [16 .. 23] : Entry 2
    //    [24 .. 31] : empty
    //    [32 .. 39] : empty
    //
    // [ HashTable ] :
    //    [40] : First chain-link for bucket 1
    //    [41] : empty
    //
    // [ Chains ] :
    //    [42] : Next chain link for bucket 1
    //    [43] : empty
    //    [44] : empty
    //    [45] : empty
    //
    template <class Derived>
    class SmallOrderedHashTable : public HeapObject {
    public:
        // Offset points to a relative location in the table
        using Offset = int;

        // ByteIndex points to a index in the table that needs to be
        // converted to an Offset.
        using ByteIndex = int;

        void Initialize(Isolate* isolate, int capacity);

        static Handle<Derived> Allocate(
            Isolate* isolate, int capacity,
            AllocationType allocation = AllocationType::kYoung);

        // Returns a true if the OrderedHashTable contains the key
        bool HasKey(Isolate* isolate, Handle<Object> key);

        // Returns a true value if the table contains the key and
        // the key has been deleted. This does not shrink the table.
        static bool Delete(Isolate* isolate, Derived table, Object key); // weolar

        // Returns an SmallOrderedHashTable (possibly |table|) with enough
        // space to add at least one new element. Returns empty handle if
        // we've already reached MaxCapacity.
        static MaybeHandle<Derived> Grow(Isolate* isolate, Handle<Derived> table);

        int FindEntry(Isolate* isolate, Object key);
        static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);

        // Iterates only fields in the DataTable.
        class BodyDescriptor;

        // Returns total size in bytes required for a table of given
        // capacity.
        static int SizeFor(int capacity)
        {
            DCHECK_GE(capacity, kMinCapacity);
            DCHECK_LE(capacity, kMaxCapacity);

            int data_table_size = DataTableSizeFor(capacity);
            int hash_table_size = capacity / kLoadFactor;
            int chain_table_size = capacity;
            int total_size = DataTableStartOffset() + data_table_size + hash_table_size + chain_table_size;

            return RoundUp(total_size, kTaggedSize);
        }

        // Returns the number elements that can fit into the allocated table.
        int Capacity() const
        {
            int capacity = NumberOfBuckets() * kLoadFactor;
            DCHECK_GE(capacity, kMinCapacity);
            DCHECK_LE(capacity, kMaxCapacity);

            return capacity;
        }

        // Returns the number elements that are present in the table.
        int NumberOfElements() const
        {
            int nof_elements = getByte(NumberOfElementsOffset(), 0);
            DCHECK_LE(nof_elements, Capacity());

            return nof_elements;
        }

        int NumberOfDeletedElements() const
        {
            int nof_deleted_elements = getByte(NumberOfDeletedElementsOffset(), 0);
            DCHECK_LE(nof_deleted_elements, Capacity());

            return nof_deleted_elements;
        }

        int NumberOfBuckets() const { return getByte(NumberOfBucketsOffset(), 0); }

        V8_INLINE Object KeyAt(int entry) const;

        DECL_VERIFIER(SmallOrderedHashTable)

        static const int kMinCapacity = 4;
        static const byte kNotFound = 0xFF;

        // We use the value 255 to indicate kNotFound for chain and bucket
        // values, which means that this value can't be used a valid
        // index.
        static const int kMaxCapacity = 254;
        STATIC_ASSERT(kMaxCapacity < kNotFound);

        // The load factor is used to derive the number of buckets from
        // capacity during Allocation. We also depend on this to calaculate
        // the capacity from number of buckets after allocation. If we
        // decide to change kLoadFactor to something other than 2, capacity
        // should be stored as another field of this object.
        static const int kLoadFactor = 2;

        // Our growth strategy involves doubling the capacity until we reach
        // kMaxCapacity, but since the kMaxCapacity is always less than 256,
        // we will never fully utilize this table. We special case for 256,
        // by changing the new capacity to be kMaxCapacity in
        // SmallOrderedHashTable::Grow.
        static const int kGrowthHack = 256;

    protected:
        static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
            int new_capacity);

        void SetDataEntry(int entry, int relative_index, Object value);

        // TODO(gsathya): Calculate all the various possible values for this
        // at compile time since capacity can only be 4 different values.
        Offset GetBucketsStartOffset() const
        {
            int capacity = Capacity();
            int data_table_size = DataTableSizeFor(capacity);
            return DataTableStartOffset() + data_table_size;
        }

        Address GetHashTableStartAddress(int capacity) const
        {
            return FIELD_ADDR(*this,
                DataTableStartOffset() + DataTableSizeFor(capacity));
        }

        void SetFirstEntry(int bucket, byte value)
        {
            DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
            setByte(GetBucketsStartOffset(), bucket, value);
        }

        int GetFirstEntry(int bucket) const
        {
            DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
            return getByte(GetBucketsStartOffset(), bucket);
        }

        // TODO(gsathya): Calculate all the various possible values for this
        // at compile time since capacity can only be 4 different values.
        Offset GetChainTableOffset() const
        {
            int nof_buckets = NumberOfBuckets();
            int capacity = nof_buckets * kLoadFactor;
            DCHECK_EQ(Capacity(), capacity);

            int data_table_size = DataTableSizeFor(capacity);
            int hash_table_size = nof_buckets;
            return DataTableStartOffset() + data_table_size + hash_table_size;
        }

        void SetNextEntry(int entry, int next_entry)
        {
            DCHECK_LT(static_cast<unsigned>(entry), Capacity());
            DCHECK_GE(static_cast<unsigned>(next_entry), 0);
            DCHECK(next_entry <= Capacity() || next_entry == kNotFound);
            setByte(GetChainTableOffset(), entry, next_entry);
        }

        int GetNextEntry(int entry) const
        {
            DCHECK_LT(entry, Capacity());
            return getByte(GetChainTableOffset(), entry);
        }

        V8_INLINE Object GetDataEntry(int entry, int relative_index);

        int HashToBucket(int hash) const { return hash & (NumberOfBuckets() - 1); }

        int HashToFirstEntry(int hash) const
        {
            int bucket = HashToBucket(hash);
            int entry = GetFirstEntry(bucket);
            DCHECK(entry < Capacity() || entry == kNotFound);
            return entry;
        }

        void SetNumberOfBuckets(int num) { setByte(NumberOfBucketsOffset(), 0, num); }

        void SetNumberOfElements(int num)
        {
            DCHECK_LE(static_cast<unsigned>(num), Capacity());
            setByte(NumberOfElementsOffset(), 0, num);
        }

        void SetNumberOfDeletedElements(int num)
        {
            DCHECK_LE(static_cast<unsigned>(num), Capacity());
            setByte(NumberOfDeletedElementsOffset(), 0, num);
        }

        static constexpr Offset PrefixOffset() { return kHeaderSize; }

        static constexpr Offset NumberOfElementsOffset()
        {
            return PrefixOffset() + (Derived::kPrefixSize * kTaggedSize);
        }

        static constexpr Offset NumberOfDeletedElementsOffset()
        {
            return NumberOfElementsOffset() + kOneByteSize;
        }

        static constexpr Offset NumberOfBucketsOffset()
        {
            return NumberOfDeletedElementsOffset() + kOneByteSize;
        }

        static constexpr Offset DataTableStartOffset()
        {
            return RoundUp<kTaggedSize>(NumberOfBucketsOffset());
        }

        static constexpr int DataTableSizeFor(int capacity)
        {
            return capacity * Derived::kEntrySize * kTaggedSize;
        }

        // This is used for accessing the non |DataTable| part of the
        // structure.
        byte getByte(Offset offset, ByteIndex index) const
        {
            DCHECK(offset < DataTableStartOffset() || offset >= GetBucketsStartOffset());
            return READ_BYTE_FIELD(*this, offset + (index * kOneByteSize));
        }

        void setByte(Offset offset, ByteIndex index, byte value)
        {
            DCHECK(offset < DataTableStartOffset() || offset >= GetBucketsStartOffset());
            WRITE_BYTE_FIELD(*this, offset + (index * kOneByteSize), value);
        }

        Offset GetDataEntryOffset(int entry, int relative_index) const
        {
            DCHECK_LT(entry, Capacity());
            int offset_in_datatable = entry * Derived::kEntrySize * kTaggedSize;
            int offset_in_entry = relative_index * kTaggedSize;
            return DataTableStartOffset() + offset_in_datatable + offset_in_entry;
        }

        int UsedCapacity() const
        {
            int used = NumberOfElements() + NumberOfDeletedElements();
            DCHECK_LE(used, Capacity());

            return used;
        }

    private:
        friend class OrderedHashMapHandler;
        friend class OrderedHashSetHandler;
        friend class OrderedNameDictionaryHandler;
        friend class CodeStubAssembler;

        OBJECT_CONSTRUCTORS(SmallOrderedHashTable, HeapObject);
    };

    class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> {
    public:
        DECL_CAST(SmallOrderedHashSet)

        DECL_PRINTER(SmallOrderedHashSet)
        EXPORT_DECL_VERIFIER(SmallOrderedHashSet)

        static const int kKeyIndex = 0;
        static const int kEntrySize = 1;
        static const int kPrefixSize = 0;

        // Adds |value| to |table|, if the capacity isn't enough, a new
        // table is created. The original |table| is returned if there is
        // capacity to store |value| otherwise the new table is returned.
        V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedHashSet> Add(
            Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key);
        V8_EXPORT_PRIVATE static bool Delete(Isolate* isolate,
            SmallOrderedHashSet table, Object key);
        V8_EXPORT_PRIVATE bool HasKey(Isolate* isolate, Handle<Object> key);

        static inline bool Is(Handle<HeapObject> table);
        static inline RootIndex GetMapRootIndex();
        static Handle<SmallOrderedHashSet> Rehash(Isolate* isolate,
            Handle<SmallOrderedHashSet> table,
            int new_capacity);
        OBJECT_CONSTRUCTORS(SmallOrderedHashSet,
            SmallOrderedHashTable<SmallOrderedHashSet>);
    };

    STATIC_ASSERT(kSmallOrderedHashSetMinCapacity == SmallOrderedHashSet::kMinCapacity);

    class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> {
    public:
        DECL_CAST(SmallOrderedHashMap)

        DECL_PRINTER(SmallOrderedHashMap)
        EXPORT_DECL_VERIFIER(SmallOrderedHashMap)

        static const int kKeyIndex = 0;
        static const int kValueIndex = 1;
        static const int kEntrySize = 2;
        static const int kPrefixSize = 0;

        // Adds |value| to |table|, if the capacity isn't enough, a new
        // table is created. The original |table| is returned if there is
        // capacity to store |value| otherwise the new table is returned.
        V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedHashMap> Add(
            Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key,
            Handle<Object> value);
        V8_EXPORT_PRIVATE static bool Delete(Isolate* isolate, // weolar
            SmallOrderedHashMap table, Object key);
        V8_EXPORT_PRIVATE bool HasKey(Isolate* isolate, Handle<Object> key);
        static inline bool Is(Handle<HeapObject> table);
        static inline RootIndex GetMapRootIndex();

        static Handle<SmallOrderedHashMap> Rehash(Isolate* isolate,
            Handle<SmallOrderedHashMap> table,
            int new_capacity);

        OBJECT_CONSTRUCTORS(SmallOrderedHashMap,
            SmallOrderedHashTable<SmallOrderedHashMap>);
    };

    STATIC_ASSERT(kSmallOrderedHashMapMinCapacity == SmallOrderedHashMap::kMinCapacity);

    // TODO(gsathya): Rename this to OrderedHashTable, after we rename
    // OrderedHashTable to LargeOrderedHashTable. Also set up a
    // OrderedHashSetBase class as a base class for the two tables and use
    // that instead of a HeapObject here.
    template <class SmallTable, class LargeTable>
    class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) OrderedHashTableHandler {
    public:
        using Entry = int;

        static Handle<HeapObject> Allocate(Isolate* isolate, int capacity);
        static bool Delete(Isolate* isolate, Handle<HeapObject> table, // weolar
            Handle<Object> key);
        static bool HasKey(Isolate* isolate, Handle<HeapObject> table,
            Handle<Object> key);

        // TODO(gsathya): Move this to OrderedHashTable
        static const int OrderedHashTableMinSize = SmallOrderedHashTable<SmallTable>::kGrowthHack << 1;
    };

    extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
        OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>;

    class V8_EXPORT_PRIVATE OrderedHashMapHandler
        : public OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap> {
    public:
        static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
            Handle<Object> key, Handle<Object> value);
        static Handle<OrderedHashMap> AdjustRepresentation(
            Isolate* isolate, Handle<SmallOrderedHashMap> table);
    };

    extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
        OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>;

    class V8_EXPORT_PRIVATE OrderedHashSetHandler
        : public OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet> {
    public:
        static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
            Handle<Object> key);
        static Handle<OrderedHashSet> AdjustRepresentation(
            Isolate* isolate, Handle<SmallOrderedHashSet> table);
    };

    class OrderedNameDictionary
        : public OrderedHashTable<OrderedNameDictionary, 3> {
    public:
        DECL_CAST(OrderedNameDictionary)

        V8_EXPORT_PRIVATE static Handle<OrderedNameDictionary> Add(
            Isolate* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
            Handle<Object> value, PropertyDetails details);

        V8_EXPORT_PRIVATE void SetEntry(Isolate* isolate, int entry, Object key,
            Object value, PropertyDetails details);

        V8_EXPORT_PRIVATE static Handle<OrderedNameDictionary> DeleteEntry(
            Isolate* isolate, Handle<OrderedNameDictionary> table, int entry);

        static Handle<OrderedNameDictionary> Allocate(
            Isolate* isolate, int capacity,
            AllocationType allocation = AllocationType::kYoung);

        static Handle<OrderedNameDictionary> Rehash(
            Isolate* isolate, Handle<OrderedNameDictionary> table, int new_capacity);

        // Returns the value for entry.
        inline Object ValueAt(int entry);

        // Set the value for entry.
        inline void ValueAtPut(int entry, Object value);

        // Returns the property details for the property at entry.
        inline PropertyDetails DetailsAt(int entry);

        // Set the details for entry.
        inline void DetailsAtPut(int entry, PropertyDetails value);

        inline void SetHash(int hash);
        inline int Hash();

        static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
        static inline RootIndex GetMapRootIndex();

        static const int kValueOffset = 1;
        static const int kPropertyDetailsOffset = 2;
        static const int kPrefixSize = 1;

        OBJECT_CONSTRUCTORS(OrderedNameDictionary,
            OrderedHashTable<OrderedNameDictionary, 3>);
    };

    extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
        OrderedHashTableHandler<SmallOrderedNameDictionary, OrderedNameDictionary>;

    class V8_EXPORT_PRIVATE OrderedNameDictionaryHandler
        : public OrderedHashTableHandler<SmallOrderedNameDictionary,
              OrderedNameDictionary> {
    public:
        static Handle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
            Handle<Name> key, Handle<Object> value,
            PropertyDetails details);
        static Handle<HeapObject> Shrink(Isolate* isolate, Handle<HeapObject> table);

        static Handle<HeapObject> DeleteEntry(Isolate* isolate,
            Handle<HeapObject> table, int entry);
        static int FindEntry(Isolate* isolate, HeapObject table, Name key);
        static void SetEntry(Isolate* isolate, HeapObject table, int entry,
            Object key, Object value, PropertyDetails details);

        // Returns the value for entry.
        static Object ValueAt(HeapObject table, int entry);

        // Set the value for entry.
        static void ValueAtPut(HeapObject table, int entry, Object value);

        // Returns the property details for the property at entry.
        static PropertyDetails DetailsAt(HeapObject table, int entry);

        // Set the details for entry.
        static void DetailsAtPut(HeapObject table, int entry, PropertyDetails value);

        static Name KeyAt(HeapObject table, int entry);

        static void SetHash(HeapObject table, int hash);
        static int Hash(HeapObject table);

        static int NumberOfElements(HeapObject table);
        static int Capacity(HeapObject table);

        static const int kNotFound = -1;

    protected:
        static Handle<OrderedNameDictionary> AdjustRepresentation(
            Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
    };

    class SmallOrderedNameDictionary
        : public SmallOrderedHashTable<SmallOrderedNameDictionary> {
    public:
        DECL_CAST(SmallOrderedNameDictionary)

        DECL_PRINTER(SmallOrderedNameDictionary)
        DECL_VERIFIER(SmallOrderedNameDictionary)

        // Returns the value for entry.
        inline Object ValueAt(int entry);

        static Handle<SmallOrderedNameDictionary> Rehash(
            Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
            int new_capacity);

        V8_EXPORT_PRIVATE static Handle<SmallOrderedNameDictionary> DeleteEntry(
            Isolate* isolate, Handle<SmallOrderedNameDictionary> table, int entry);

        // Set the value for entry.
        inline void ValueAtPut(int entry, Object value);

        // Returns the property details for the property at entry.
        inline PropertyDetails DetailsAt(int entry);

        // Set the details for entry.
        inline void DetailsAtPut(int entry, PropertyDetails value);

        inline void SetHash(int hash);
        inline int Hash();

        static const int kKeyIndex = 0;
        static const int kValueIndex = 1;
        static const int kPropertyDetailsIndex = 2;
        static const int kEntrySize = 3;
        static const int kPrefixSize = 1;

        // Adds |value| to |table|, if the capacity isn't enough, a new
        // table is created. The original |table| is returned if there is
        // capacity to store |value| otherwise the new table is returned.
        V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedNameDictionary> Add(
            Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
            Handle<Name> key, Handle<Object> value, PropertyDetails details);

        V8_EXPORT_PRIVATE void SetEntry(Isolate* isolate, int entry, Object key,
            Object value, PropertyDetails details);

        static inline RootIndex GetMapRootIndex();

        OBJECT_CONSTRUCTORS(SmallOrderedNameDictionary,
            SmallOrderedHashTable<SmallOrderedNameDictionary>);
    };

} // namespace internal
} // namespace v8

#include "src/objects/object-macros-undef.h"

#endif // V8_OBJECTS_ORDERED_HASH_TABLE_H_
